package com.xianggu.Collection.map;

import java.util.Iterator;

/**
 * @author chengjy
 * @date 2025/4/3
 */
public class MyHashMap<K, V> implements Iterable<MyHashMap.Node>{

    private Node[] table = new Node[16];

    private int size;

    public void put(K key, V value) {
        // 1. 获取索引
        int index = indexOf(key , table.length);
        // 2. 判断索引位置是否有值
        if (table[index] == null) {
            table[index] = new Node<>(key, value);
            size++;
            resize();
        }else{
            // 3. 如果有值，获取头结点
            Node<K, V> head = table[index];
            // 4. 遍历链表，判断key是否存在
            while (head.next != null){
                if (head.key.equals(key)){
                    head.value = value;
                }else {
                    head = head.next;
                }
            }
            // 5. 如果key不存在，则添加到链表尾部
            head.next = new Node<>(key, value);
            size++;
            resize();
        }
    }

    public V get(K key) {
        // 1. 获取索引
        int index = indexOf(key , table.length);
        // 2. 判断索引位置是否有值
        if (table[index] == null) {
            return null;
        }else{
            // 3. 如果有值，获取头结点
            Node<K, V> head = table[index];
            // 4. 遍历链表，判断key是否存在
            while (head.next != null){
                if (head.key.equals(key)){
                    return head.value;
                }else {
                    head = head.next;
                }
            }
        }
        // 5. 如果key不存在，则返回null
        return null;
    }

    public V remove(K key) {// 1. 获取索引
        int index = indexOf(key , table.length);
        // 2. 判断索引位置是否有值
        if (table[index] == null) {
            return null;
        }else{
            // 3. 如果有值，获取头结点
            Node<K, V> pre = table[index];

            if(pre.key.equals(key)){
                table[index] = pre.next;
                size--;
                return pre.value;
            }

            Node<K, V> current = pre.next;
            // 4. 遍历链表，判断key是否存在
            while (current.next != null){
                if (current.key.equals(key)){
                    // 需要删除当前节点，并返回value
                    pre.next = current.next;
                    size--;
                    return current.value;
                }else {
                    pre = current;
                    current = current.next;
                }
            }
            return null;
        }
    }

    //扩容方法
    private void resize() {
        // 1. 判断是否需要扩容
        if(size < table.length * 0.75){
            return;
        }

        // 2. 创建新数组，长度为原数组的两倍
        Node[] newTable = new Node[table.length * 2];
//        System.out.println(String.format("扩容数组：由%s 扩容为 %s" , table.length , newTable.length));

        // 3. 遍历原数组，将元素重新hash到新数组中
        for (int i = 0; i < table.length; i++) {
            // 老元素
            Node<K ,V> oldHead = table[i];
            if(oldHead == null){
                // 跳过本次
                continue;
            }
            while (oldHead != null) {
                int index = indexOf(oldHead.key , newTable.length);
                // 新数组中对应索引位置
                Node<K ,V> newHead = newTable[index];
                // 提前获取下一次的循环条件
                Node next = oldHead.next;
                oldHead.next = null;

                if(newHead == null){
                    newTable[index] = oldHead;
                }else {
                    // 头插法，将当前节点的 next执行 头结点原来的元素，头结点执行当前节点
                    oldHead.next = newHead;
                    newTable[index] = oldHead;
                }
                // 循环条件
                oldHead = next;
            }
        }
        this.table = newTable;
    }

    public int size() {
        return size;
    }

    private int indexOf(Object key , int length){
//        return key.hashCode() % length;
        return key.hashCode() & length-1;
    }

    public boolean containsKey(K key) {
        // 1. 获取索引
        int index = indexOf(key , table.length);
        // 2. 判断索引位置是否有值
        if (table[index] == null) {
            return false;
        }else{
            // 3. 如果有值，获取头结点
            Node<K, V> head = table[index];
            // 4. 遍历链表，判断key是否存在
            while (head.next != null){
                if (head.key.equals(key)){
                    return true;
                }else {
                    head = head.next;
                }
            }
        }
        return false;
    }

    @Override
    public Iterator<MyHashMap.Node> iterator() {
        return new MyHashMapIterator(table , size);
    }

    class MyHashMapIterator implements Iterator<MyHashMap.Node> {
        private Node[] table;
        private int nextIndex = 0;
        private Node currentInterior = null;

        private int count;
        private int sizeInter = 0;

        public MyHashMapIterator(Node[] table , int size) {
            this.table = table;
            this.count = 1;
            this.sizeInter = size;

            for (int i = 0; i < table.length; i++) {
                if (table[i] == null) {
                    continue;
                }
                nextIndex = i +1;
                currentInterior = table[i];
                break;
            }
        }

        @Override
        public boolean hasNext() {
            return count <= sizeInter;
        }

        @Override
        public MyHashMap.Node next() {
            // 遍历当前节点
            Node current = currentInterior;

            if(currentInterior.next != null){
                currentInterior = currentInterior.next;
            }else{
                for (int i = nextIndex; i < table.length; i++) {
                    if (table[i] == null) {
                        continue;
                    }
                    nextIndex = i + 1;
                    currentInterior = table[i];
                    break;
                }
            }
            count++;
            return current;
        }
    }
    public class Node<K, V> {
        K key;
        V value;
        Node next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}
